Many media, such as wireless telephony, optical data transmission and the like accomplish communication by sending and receiving of binary digits, or bits, over a communication channel. Almost every communication channel introduces impediments to transmission, such as noise or extraneous signals, so that it is very difficult or impossible to be certain of the identity of any particular bit, that is, whether a bit is a binary 0 or a binary 1. Therefore, communication is frequently accomplished through the use of binary codes. Many binary codes provide error control, allowing for detection of errors in transmission or for correction of the errors. A coding arrangement imposes constraints on bit sequences that are introduced to the transmission side of a channel, such that the bit sequence received at the receiving side of a channel will follow some known criterion. If the bits at the receiving side of the channel do not follow the specified criterion, it is known that an error occurred during transmission, and it is also frequently possible to identify and correct the specific error. Transmissions often take the form of codewords, where a codeword is a sequence of bits following a criterion imposed by a coding arrangement.
One particularly useful error correcting code is a low density parity check (LDPC) code. Such a code is conveniently represented by a bipartite graph having a set of n “variable” nodes and a set of (n−k) “check” nodes, where n is the total number of bits in a codeword to be transmitted and k is the number of information bits in the codeword. A set of edges connects variable nodes to check nodes. The connectivity of the graph defines a particular LDPC code. To determine whether a binary vector of length n is a valid codeword, the vector is placed into 1:1 correspondence with the variable nodes. At the check nodes, the bits are summed as determined by the edges of the graph. The vector is a codeword if and only if the modulo 2 sum of the bits at each check node is 0. For example, a check node “C” may be connected to two variable nodes “A” and “B”. A binary vector “01” is tested by placing the bit “0” into correspondence with the node “A” and the bit “1” into correspondence with the node “B.” The node “C” is connected to the nodes “A” and “B”, and therefore the bits “0” and “1” are summed to determine if the vector “01” is a valid codeword. In this case, the modulo 2 sum of the bits is “1,” so the codeword is invalid.
In order to decode an LDPC code, the decoder passes a posteriori probabilities of the two possible values of each input node to the check nodes. At the check nodes, the parity condition is used to calculate new a posteriori probabilities, which are passed back to the variable nodes. This process iterates to convergence.
An LDPC code is most useful if its rate is high, the codeword length n is relatively short, the minimum distance, which relates to distinguishability between codewords when noise is present, is relatively high and the time required to converge is relatively short. However, it is difficult or impossible to design a code that achieves all four of these conditions at the same time, so that code designs typically seek to strike a balance between the conditions, while insuring that the code provides acceptable performance. In particular, it is essential that a code be designed so that convergence can proceed successfully. Some faulty designs exist that will prevent convergence, so that decoding is impossible. The design of a code prevents convergence when values associated with selected information transfer properties of the check nodes at any point during the convergence process exceed those of the variable nodes at any point. Such a condition can be identified by examining an extrinsic information transfer function chart, or EXIT chart. An EXIT chart predicts the behavior of a code, and plots the information transfer characteristics of the code for both the variable nodes and the check nodes of the code. If the code is such that the plot for the check nodes lies above the plot for the variable nodes at any point on the chart, decoding to convergence is impossible. On the other hand, the area enclosed between the plot for the check nodes and the plot for the variable nodes indicates the code rate, so that ideally codes should be designed such that the two plots lie as close together as possible. However, the closer together the plots lie, the more difficult it is to insure that the check node plot never crosses the variable node plot.
For conventional LDPC codes, achieving near channel capacity may often require relatively long codes or many iterations in decoding, as compared to codes that could be developed more freely so as to yield desired characteristics.
There exists, therefore, a need for systems and techniques for designing codes that allow flexibility in design and that allow for a relatively high code rate and insure proper convergence.